package ctp.ctpgraph;

import java.awt.Color;
import java.awt.Dimension;
import java.awt.Paint;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import javax.swing.JFrame;

import org.apache.commons.collections15.Transformer;

import edu.uci.ics.jung.algorithms.layout.FRLayout;
import edu.uci.ics.jung.algorithms.layout.Layout;
import edu.uci.ics.jung.algorithms.layout.TreeLayout;
import edu.uci.ics.jung.graph.DelegateTree;
import edu.uci.ics.jung.graph.Graph;
import edu.uci.ics.jung.graph.SparseGraph;
import edu.uci.ics.jung.visualization.BasicVisualizationServer;
import edu.uci.ics.jung.visualization.renderers.Renderer.VertexLabel.Position;

public class CTPGraph { 

	Graph<Vertex, Edge> graph;
	DelegateTree<Vertex, Edge> tree;
	Map<Integer,Double> dGapMap;
	Map<Integer,Double> dRatioMap;
	

	Vertex start = null;
	Vertex goal = null;

	public CTPGraph() {
		super();
		this.graph = new SparseGraph<Vertex, Edge>();
		this.tree = new DelegateTree<Vertex, Edge>();
	}

	public Vertex getStart() {
		return start;
	}

	public void setStart(Vertex start) {
		this.start = start;
	}

	public Vertex getGoal() {
		return goal;
	}

	public void setGoal(Vertex goal) {
		this.goal = goal;
	}

	public Graph<Vertex, Edge> getGraph() {
		return this.graph;
	}
	
	public DelegateTree<Vertex, Edge> getTree() {
		return this.tree;
	}

	private void drawLayout(Layout<Vertex,Edge> layout) {
		

		BasicVisualizationServer<Vertex, Edge> vv = new BasicVisualizationServer<Vertex, Edge>(layout);

		vv.setPreferredSize(new Dimension(700, 700));
		Transformer<Vertex, Paint> vertexPaint = new Transformer<Vertex, Paint>() {
			public Paint transform(Vertex i) {
				if (i == start ) {
					return Color.GREEN;
				} else if (i == goal) {
					return Color.RED;
				} else {
					return Color.GRAY;
				}
			}
		};

		vv.getRenderContext().setVertexFillPaintTransformer(vertexPaint);
		//vv.getRenderContext().setVertexLabelTransformer(new ToStringLabeller<Vertex>());
		vv.getRenderContext().setVertexLabelTransformer(new Transformer<Vertex, String>() {

			@Override
			public String transform(Vertex v) {
				return v.name;
			}
			
		});
		//vv.getRenderContext().setEdgeLabelTransformer(new ToStringLabeller<Edge>());
		vv.getRenderContext().setEdgeLabelTransformer(new Transformer<Edge, String>() {

			@Override
			public String transform(Edge e) {
				return e.name;
			}
		});
		vv.getRenderContext().setLabelOffset(20);
		vv.getRenderer().getVertexLabelRenderer().setPosition(Position.CNTR);

		JFrame frame = new JFrame("Simple Graph View");
		frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
		frame.getContentPane().add(vv);
		frame.pack();
		frame.setVisible(true);
		
	}
	
	public void drawGraph() {
		Layout<Vertex, Edge> layout = new FRLayout<Vertex, Edge>(this.graph);
		layout.setSize(new Dimension(400, 400));
		drawLayout(layout);
	}
	
	public void drawTree() {
		Layout<Vertex, Edge> layout = new TreeLayout<Vertex, Edge>(this.tree,150,150);
		drawLayout(layout);
	}
	
	public double infinityCost() {
		return 1000000.0;
	}
	
	public void rollGraph(Graph<Vertex, EdgeRandom> abstractGraph) {
		
		for (EdgeRandom edgeRandom : abstractGraph.getEdges()) {			
			Edge edge = edgeRandom.generateEdge();
			graph.addEdge(edge, abstractGraph.getEndpoints(edgeRandom));			
		}
		
		buildTreeFromGraph();
		
	}

	private void buildTreeFromGraph() {
		tree.addVertex(start);		
		// Not adding edges that have the goal
		
		Collection<Edge> edges = new HashSet<Edge>(graph.getEdges());
		while (edges.size() > 0) {
			Set<Edge> edgesToRemove = new HashSet<Edge>();
			for (Edge edge : edges) {
				if(graph.getEndpoints(edge).contains(goal)) {
					edgesToRemove.add(edge);
					continue;
				}
				boolean parentVertex = true;
				for (Vertex vertex : graph.getIncidentVertices(edge)) {
					if (parentVertex) {
						if (tree.containsVertex(vertex)) {
							tree.addEdge(edge, graph.getIncidentVertices(edge));
							edgesToRemove.add(edge);
							break;
						}					
						//parentVertex = false;
					}					
				}
			}
			edges.removeAll(edgesToRemove);
		}
	}

	void calculateCostBlockedSubtree() {
		
	}
	
	public void calculateSubtreeProperties(Vertex v) {
		if (tree.getChildCount(v) == 0) {
			v.setExpectedCostSubtree(0.0);
			v.setProbBlockedSubtree(0.0);
			v.setdSubtree(0.0);
						
			if (tree.getInEdges(v).size() != 1) {
				throw new RuntimeException("more than a single parent to leaf");
			}
			
			for(Edge inEdge : tree.getInEdges(v)) {
				v.setProbBlockedSubtreeParent(inEdge.getProbBlocked());
				v.setExpectedCostSubtreeParent((1-inEdge.getProbBlocked()) * inEdge.getCost());
				v.setdSubtreeParent(inEdge.getCost());
			}
			
			
		} else {
			double childrenBlockedProb = 1.0;
			for(Vertex childOfRoot : tree.getChildren(v)) {
				calculateSubtreeProperties(childOfRoot);
				childrenBlockedProb *= childOfRoot.getProbBlockedSubtreeParent();
			}
			
			v.setProbBlockedSubtree(childrenBlockedProb);
			
			
			v.setExpectedCostSubtree(calcExpectedCostSubTree(v));
			
			if (tree.getInEdges(v).size() > 1) {
				throw new RuntimeException("more than a single parent to leaf");
			}
			
			for(Edge inEdge : tree.getInEdges(v)) {
				v.setProbBlockedSubtreeParent(inEdge.getProbBlocked() + (1-inEdge.getProbBlocked()) * v.getProbBlockedSubtree());
				v.setExpectedCostSubtreeParent((1-inEdge.getProbBlocked()) * (inEdge.getCost() + v.getExpectedCostSubtree() + (v.getProbBlockedSubtree() * inEdge.getCost())));
			}

			v.setdSubtree(v.getExpectedCostSubtree() / (1-v.getProbBlockedSubtree()));
			if (!tree.isRoot(v)) {
				v.setdSubtreeParent(v.getExpectedCostSubtreeParent() / (1 - v.getProbBlockedSubtreeParent()));
			}
		}
	}
	
	private Double calcExpectedCostSubTree(Vertex v) {
		Collection<Vertex> childrenCollection = tree.getChildren(v);
		List<Vertex> childrenList = new ArrayList<Vertex>(childrenCollection);
		Collections.sort(childrenList, new Comparator<Vertex>() {

			@Override
			public int compare(Vertex v1, Vertex v2) {
				return v1.getdSubtreeParent().compareTo(v2.getdSubtreeParent());
			}
			
		});
		
		double sumExpectedCost = 0.0;
		for (int n = 0; n < childrenList.size(); n++) {
			double countProbability = 1.0;
			for (int i = 0; i < n; i++) {
				countProbability *= childrenList.get(i).getProbBlockedSubtreeParent();
			}
			sumExpectedCost += countProbability * childrenList.get(n).getExpectedCostSubtreeParent(); 
		}
		
		return sumExpectedCost;
	}
	
	private List<Vertex> getVerticesAtDepth(int depth) {
		List<Vertex> verticesAtDepth = new ArrayList<Vertex>();
		
		for (Vertex v : tree.getVertices()) {
			if (v.isDefault()) {
				continue;
			}
			if (tree.getDepth(v) == depth) {
				verticesAtDepth.add(v);
			}
		}
		
		Collections.sort(verticesAtDepth, new Comparator<Vertex>() {
			@Override
			public int compare(Vertex v1, Vertex v2) {
				return v1.getdSubtreeParent().compareTo(v2.getdSubtreeParent());
			}
		});		
		
		
		return verticesAtDepth;
	}
	
	public void populateDGapMap() {
		this.dGapMap   = new HashMap<Integer, Double>();
		this.dRatioMap = new HashMap<Integer, Double>();
		for (int depth = 1; depth <= tree.getHeight(); depth++) {
			List<Vertex> vertexAtDepthSorted = getVerticesAtDepth(depth);
			double gap = 
					vertexAtDepthSorted.get(vertexAtDepthSorted.size()-1).getdSubtreeParent() 
					- vertexAtDepthSorted.get(0).getdSubtreeParent();
			double ratio = 
					vertexAtDepthSorted.get(vertexAtDepthSorted.size()-1).getdSubtreeParent() 
					/ vertexAtDepthSorted.get(0).getdSubtreeParent();
					
			this.dGapMap.put(depth, gap);
			this.dRatioMap.put(depth, ratio);
		}
	}
	
	public double maxDGap() {
		return Collections.max(this.dGapMap.values());
	}
	
	public double maxDRatio() {
		return Collections.max(this.dRatioMap.values());
	}
	
	public boolean isDSubtreeBiggerThanParentCost() {
		for (Vertex vertex : this.tree.getVertices()) {
			if (tree.getRoot().equals(vertex)) {
				continue;
			}
			
			Edge parentEdge = tree.getParentEdge(vertex);
			if (vertex.getdSubtreeParent() > parentEdge.cost) {
				return true;
			}
		}
		return false;
	}
	
}
